Man kann zeigen,\footnote{\buchmann{3.21 und 3.22}, Beweis haben wir aber nicht behandelt.} dass die multiplikative Gruppe eines endlichen Körpers $GF(p^k)$ zyklisch ist, d.h.\ dass sich alle von Null verschiedenen Elemente als Potenz $g^i$ eines Erzeugers $g$ schreiben lassen.

Insbesondere gilt für $GF(p)$, was ja gerade $\Z/p\Z$ entspricht, dass $(\Z/p\Z)^*$ zyklisch ist, d.h.\ es gibt eine Restklasse $g := m + p\Z$, so dass deren Potenzen $g^i$ alle Elemente in $(\Z/p\Z)^* = \{ 1 + p\Z, \ldots, (p-1) + p\Z \}$ ergeben. Ein solches $g$ nennt man \emph{Erzeuger} oder auch \emph{Primitivwurzel modulo $p$}. (In der Lösung zu Aufgabe (ix) des vorigen Übungsblatts wurde der Fall $p = 7, m = 3$ betrachtet.)

Schreiben Sie ein Java-Programm, welches bei Eingabe einer Primzahl $p$ für alle Restklassen $m + p \Z$, wo $1 \le m < p$, deren Ordnung in $(\Z/p\Z)^*$ ausgibt und ermittelt, wie viele davon Primitivwurzeln sind.

Führen Sie Ihr Programm für $p = 23$ und $p = 31$ aus.

\textbf{Lösung}

Die nachfolgende Tabelle zeigt das Ergebnis für $p = 23$. Primitivwurzeln sind hervorgehoben.

\begin{center}
\begin{tabular}{|c|c||c|c||c|c||c|c|}
\hline
Restklasse & Ordnung & Restklasse & Ordnung & Restklasse & Ordnung & Restklasse & Ordnung \\
\hline 
1 & 1 & \cellcolor{dunkelgrau}7 & \cellcolor{dunkelgrau}22 & 13 & 11 & \cellcolor{dunkelgrau}19 & \cellcolor{dunkelgrau}22 \\
\hline
2 & 11 & 8 & 11 & \cellcolor{dunkelgrau}14 & \cellcolor{dunkelgrau}22 & \cellcolor{dunkelgrau}20 & \cellcolor{dunkelgrau}22 \\
\hline
3 & 11 & 9 & 11 & \cellcolor{dunkelgrau}15 & \cellcolor{dunkelgrau}22 & \cellcolor{dunkelgrau}21 & \cellcolor{dunkelgrau}22 \\
\hline
4 & 11 & \cellcolor{dunkelgrau}10 & \cellcolor{dunkelgrau}22 & 16 & 11 & 22 & 2 \\
\hline
\cellcolor{dunkelgrau}5 & \cellcolor{dunkelgrau}22 & \cellcolor{dunkelgrau}11 & \cellcolor{dunkelgrau}22 & \cellcolor{dunkelgrau}17 & \cellcolor{dunkelgrau}22 & & \\
\hline
6 & 11 & 12 & 11 & 18 & 11 & & \\
\hline
\end{tabular}
\end{center}

Die nachfolgende Tabelle zeigt das Ergebnis für $p = 31$. Primitivwurzeln sind hervorgehoben.

\begin{center}
\begin{tabular}{|c|c||c|c||c|c||c|c|}
\hline
Restklasse & Ordnung & Restklasse & Ordnung & Restklasse & Ordnung & Restklasse & Ordnung \\
\hline 
1 & 1 & 9 & 15 & \cellcolor{dunkelgrau}17 & \cellcolor{dunkelgrau}30 & 25 & 3 \\
\hline
2 & 5 & 10 & 15 & 18 & 15 & 26 & 6 \\
\hline
\cellcolor{dunkelgrau}3 & \cellcolor{dunkelgrau}30 & \cellcolor{dunkelgrau}11 & \cellcolor{dunkelgrau}30 & 19 & 15 & 27 & 10 \\
\hline
4 & 5 & \cellcolor{dunkelgrau}12 & \cellcolor{dunkelgrau}30 & 20 & 15 & 28 & 15 \\
\hline
5 & 3 & \cellcolor{dunkelgrau}13 & \cellcolor{dunkelgrau}30 & \cellcolor{dunkelgrau}21 & \cellcolor{dunkelgrau}30 & 29 & 10 \\
\hline
6 & 6 & 14 & 15 & \cellcolor{dunkelgrau}22 & \cellcolor{dunkelgrau}30 & 30 & 2 \\
\hline
7 & 15 & 15 & 10 & 23 & 10 & & \\
\hline
8 & 5 & 16 & 5 & \cellcolor{dunkelgrau}24 & \cellcolor{dunkelgrau}30 & & \\
\hline
\end{tabular}
\end{center}